package leetcode.weekly.week309;

import java.util.HashMap;
import java.util.Map;

//Solution2Test
public class Solution2 {

	int mod = (int) 1e9 + 7;

	public int numberOfWays(int startPos, int endPos, int k) {
		Map<Integer, Map<Integer, Long>> dp = new HashMap<>();
		long ans = this.find(startPos, endPos, k, dp);
		ans %= mod;
		return (int) ans;
	}

	private long find(int s, int e, int k, Map<Integer, Map<Integer, Long>> dp) {
		if (k == 0) {
			return s == e ? 1 : 0;
		}
		if (dp.containsKey(e) && dp.get(e).containsKey(k)) {
			return dp.get(e).get(k);
		}
		long ans = 0;
		ans += this.find(s, e + 1, k - 1, dp);
		ans %= mod;
		ans += this.find(s, e - 1, k - 1, dp);
		ans %= mod;
		Map<Integer, Long> map = new HashMap<>();
		map.put(k, ans);
		dp.put(e, map);
		return ans;
	}

}
